package com.yeung.Backtracking;

/**
 * 求一列数组的全排列
 */
public class 求n个元素的幂集合 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3};
        //用来记录中间结果, 是否需要这个item
        int[] isNeed = new int[arr.length];
        for (int i = 0; i < isNeed.length; i++) isNeed[i] = 0;//初始化所有都不要
        powerSet(arr, isNeed, 0, arr.length);

    }

    /**
     * 利用回溯的方法,进行集合的选取,
     * 类似于简化版的背包问题
     *
     * @param items 集合中的元素
     * @param i
     * @param n     集合中元素的个数
     */
    private static void powerSet(int[] items, int[] isNeed, int i, int n) {
        //1. 求含有n个元素的集合A幂集合, 进入函数时一堆A中前i-1个元素做了取舍处理
        //2. 现在重第i个元素起开始进行取舍处理. 若i>n, 则求得幂集的一个元素, 并输出
        //初始调用PowerSet(1,n);
        if (i == n - 1) {
            // output subset with element i
            isNeed[i] = 1;
            for (int j = 0; j < n; j++) {
                if (isNeed[j] != 0)
                    System.out.print(items[j] + " ");
            }
            System.out.println();

            // output subset without element i
            isNeed[i] = 0;
            for (int j = 0; j < n; j++) {
                if (isNeed[j] != 0)
                    System.out.print(items[j] + " ");
            }
            System.out.println();

        } else {
            //取第i个元素
            //generate all subsets with i included
            isNeed[i] = 1;
            powerSet(items, isNeed, i + 1, n);

            //舍去第i个元素
            // generate all subsets with i out
            isNeed[i] = 0;
            powerSet(items, isNeed, i + 1, n);
        }
    }


}
